package com.xj.algorithm.leetcode;

/**
 * 实现 strStr()
 * 在一个字符串中找出另一个字符串出现的第一个位置
 */
public class L28_在一个字符串中找出另一个字符串出现的第一个位置 {

    /**
     *实现 strStr() 函数。
     *
     * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
     *
     * 示例 1:
     * 输入: haystack = "hello", needle = "ll"
     * 输出: 2
     *
     * 示例 2:
     * 输入: haystack = "aaaaa", needle = "bba"
     * 输出: -1
     * 说明:
     *
     * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     *
     * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
     */

    public static void main(String[] args) {
        String haystack1 = "hello", needle1 = "ll";
        System.out.println(strStrGood(haystack1,needle1));

        String haystack2 = "aaaaa", needle2 = "bba";
        System.out.println(strStrGood(haystack2,needle2));
    }

    //我的解法：直接使用api
    public static int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    //暴力匹配算法
    public static int strStrEasy(String haystack, String needle) {
        int haystakLength=haystack.length();
        int needleLength=needle.length();

        for (int i = 0; i < haystakLength - needleLength; i++) {
            int j;
            for (j = 0; j < needleLength; j++) {
                if (needle.substring(j,j+1) != haystack.substring(i+j,i+j+1)){
                    break;
                }
            }

            if (j == needleLength){
                return i;
            }
        }
        return -1;
    }

    //精彩解法：KMP算法。这是动态规划。本质是状态机的不同转化，dp数组就是状态转移数组
    /**
     *dp[j][c] = next
     * 0 <= j < M，代表当前的状态
     * 0 <= c < 256，代表遇到的字符（ASCII 码）
     * 0 <= next <= M，代表下一个状态
     *
     * dp[4]['A'] = 3 表示：
     * 当前是状态 4，如果遇到字符 A，
     * pat 应该转移到状态 3
     *
     * 当某个状态无法推进时，问它的影子状态(相同前缀)，如果能推进，则进入影子状态的位置
     * 否则继续问影子的影子，直到回到起点
     *
     * 状态机的创建比较复杂。影子状态一开始都是0状态，影子状态有点类似与快慢指针，遇到相同值的状态转移是不一样的。
     */
    public static int strStrGood(String haystack, String needle) {
        //1.根据模式字符串构造状态机--比较难
        int haystackLength = haystack.length();
        int needleLength = needle.length();

        // dp[状态][字符] = 下个状态, 影子状态 X 初始为 0
        int[][] dp = new int[needleLength][256];
        dp[0][needle.charAt(0)] = 1;    //🌿🌿🌿
        int X = 0;
        // 当前状态 j 从 1 开始
        for (int j = 1; j < needleLength; j++) {
            for (int c = 0; c < 256; c++) {
                if (needle.charAt(j) == c)
                    dp[j][c] = j + 1;
                else
                    dp[j][c] = dp[X][c];    //回退委托给影子状态
            }

            // 当前是状态X，遇到字符 needle.charAt(j)，更新影子状态
            X = dp[X][needle.charAt(j)];    //🌿🌿🌿
        }

        //2.根据状态机和给定目标字符串，找到第一个位置
        int j = 0;
        for (int i = 0; i < haystackLength; i++) {
            // 当前是状态 j，遇到字符haystack.charAt(i)，得到最新状态
            j = dp[j][haystack.charAt(i)];

            if (j == needleLength) {
                return i - needleLength + 1;
            }
        }
        return -1;
    }

}
